package jp.dip.hael.gameai.graph.searcher
{
	import jp.dip.hael.gameai.graph.Edge;
	import jp.dip.hael.gameai.graph.GraphEx;
	import jp.dip.hael.gameai.graph.WeightedEdge;
	
	import mx.collections.ArrayCollection;
	
	/**
	 * 幅優先探索
	 */
	public class BFS extends Searcher
	{
		/**
		 * コンストラクタ
		 * 
		 * @param graph 探索対象のグラフ
		 */
		public function BFS(graph:GraphEx)
		{
			super(graph);
		}
		
		
		/**
		 * @inheritDoc
		 */
		override public function search(src:int, dst:int):Boolean
		{
			var queue:Array /* of Edge */ = [];
			queue.push(new Edge(src, src));
			
			var visited:Array /* of Boolean */ = new Array(graphRef_.size);
			visited[src] = true;
			
			var route:Array /* of int */ = new Array(graphRef_.size);
			
			while(queue.length > 0){
				var next:Edge = queue.shift();
				route[next.dst] = next.src;
				
				if(next.dst == dst){
					src_ = src;
					dst_ = dst;
					route_ = route;
					found_ = true;
					return true;
				}
				
				var dsts:Array = graphRef_.edge(next.dst);
				for each(var e:Edge in dsts){
					if(!visited[e.dst]){
						queue.push(e);
						visited[e.dst] = true;
					}
				}
			}
			
			return false;
		}
		/**
		 * @inheritDoc
		 */
		override public function searchAll(src:int, dst:int, visited:ArrayCollection) : void
		{
			var nodes:Array = new Array();
			if(!(graphRef_.edge(src) is Array))
			{
				return;
			}
			for(var i:int=0;i<graphRef_.edge(src).length;i++)
			{
				nodes.push( (graphRef_.edge(src)[i] as WeightedEdge).dst );
			}
			//trace("nodes:",nodes);
			for(var node:* in nodes)
			{
				//trace("~node:",node,"nodes[node]",nodes[node]);
				if(visited.contains(nodes[node]))
				{
					continue;
				}
				if(int(nodes[node])==dst)
				{
					visited.addItem(nodes[node]);
					//restore this path.
					saveToAllSimplePaths(visited);
					visited.removeItemAt(visited.length-1);
					break;
				}
			}
			// in breadth-first, recursion needs to come after visiting adjacent nodes
			for(var node2:* in nodes)
			{
				//trace("~~node:",node,"nodes[node]",nodes[node]);
				if(visited.contains(nodes[node2])||int(nodes[node2])==dst)
				{
					continue;
				}
				visited.addItem(nodes[node2]);
				searchAll(nodes[node2],dst,visited);
				visited.removeItemAt(visited.length-1);
			}
		}
		
	}
}
